/**
 * @Author: ColorSheep
 * @Date: 27 6月 2025 21:52
 * @Version: 1.0
 * @Description: 双向链表, prev和next要一起绑定才有效
 */

public class MyLinkedList<E> implements MyList<E> {
    
    
    // transient关键字修饰的变量不参与序列化, 一般用于存储临时数据, 比如数据常常变, 但是不参与序列化.
    // 节省存储空间
    transient int size;
    
    transient Node<E> firstNode;
    
    transient Node<E> lastNode;
    
    void linkFirst(E data) {
        final Node<E> oldFirst = firstNode; // 先将旧的头节点保存起来
        Node<E> newNode = new Node<>(null, data, oldFirst);// 创建新节点, 且前置节点为null
        firstNode = newNode; // 头结点设置为新节点, 因为是头插
        if (null == oldFirst) {
            lastNode = newNode; // 此处等于firstNode也行, 没有节点时首尾节点是同一个
        } else {
            oldFirst.prevNode = newNode; // 将旧的头节点的前驱节点设置为新节点
        }
        size++;
    }
    
    
    void linkLast(E data) {
        final Node<E> oldLast = lastNode; // 先将旧的尾节点保存起来
        Node<E> newNode = new Node<>(oldLast, data, null);// 创建新节点, 且前置节点为oldLast
        lastNode = newNode; // 尾结点设置为新节点, 因为是尾插
        if (null == oldLast) {
            firstNode = newNode; // 此处等于lastNode也行, 没有节点时首尾节点是同一个
        } else {
            // 直接设置头结点相关的就好了, 尾结点不需要变, 因为是头插
            oldLast.nextNode = newNode; // 将旧的头节点的后继节点设置为新节点
        }
        size++;
    }
    
    Node<E> nodeByIndex(int index) {
        Node<E> current;
        // 二分查找: 降低时间复杂度
        if (index < (size >> 1)) { // 从前往后遍历
            current = firstNode;
            for (int i = 0; i < index; i++) {
                current = current.nextNode;
            }
        } else { // 从后往前遍历
            current = lastNode;
            for (int i = size - 1; i > index; i--) {
                current = current.prevNode;
            }
        }
        return current;
    }
    
    
    void unLink(Node<E> toUnLink) {
        Node<E> prevNode = toUnLink.prevNode;
        Node<E> nextNode = toUnLink.nextNode;
        if (null == prevNode) {
            firstNode = nextNode; // 删除的就是第一个节点, 那么直接设置头结点即可
        } else {
            prevNode.nextNode = nextNode;
            toUnLink.prevNode = null; // 将删除节点的前驱节点置空, 防止内存泄漏
        }
        size--;
    }
    
    void unLinkLast() {
        Node<E> oldLastNode = lastNode;
        Node<E> prevNode = lastNode.prevNode;
        lastNode = prevNode;
        if (null == prevNode) {
            firstNode = null;
        } else {
            prevNode.nextNode = null;
            oldLastNode.prevNode = null;
        }
        size--;
    }
    
    
    void unLinkFirst(){
        Node<E> oldFirstNode = firstNode;
        Node<E> nextNode = firstNode.nextNode;
        firstNode = nextNode;
        if (null == nextNode) {
            lastNode = null;
        } else {
            nextNode.prevNode = null;
            oldFirstNode.nextNode = null;
        }
        size--;
    }
    
    @Override
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    @Override
    public boolean addFirst(E e) {
        linkFirst(e);
        return true;
    }
    
    @Override
    public boolean addLast(E e) {
        linkLast(e);
        return true;
    }
    
    void validate(int index) {
        if (size == 0) {
            throw new IndexOutOfBoundsException("链表为空");
        }
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界");
        }
    }
    
    @Override
    public E get(int index) {
        validate(index);
        //双向链表无法通过index获取节点, 只能从头遍历, 迭代器实现, 效率很低
        return nodeByIndex(index).data;
    }
    
    @Override
    public E getFirst() {
        if (null == firstNode)
            return null;
        return firstNode.data;
    }
    
    
    @Override
    public E getLast() {
        if (null == lastNode)
            return null;
        return lastNode.data;
    }
    
    @Override
    public boolean remove(int index) {
        validate(index);
        if (index == 0) {
            unLinkFirst();
        } else if (index == size - 1) {
            unLinkLast();
        } else {
            Node<E> current = nodeByIndex(index);
            unLink(current);
        }
        return true;
    }
    
    
    @Override
    public boolean remove(E e) {
        Node<E> current = firstNode;
        while (current != null) {
            if ((e == null && current.data == null) || (current.data.equals(e))) {
                unLink(current);
                return true;
            }
            current = current.nextNode;
        }
        return false; // 找不到元素返回 false
    }
    
    @Override
    public boolean removeFirst() {
        unLinkFirst();
        return true;
    }
    
    @Override
    public boolean removeLast() {
        unLinkLast();
        return true;
    }
    
    @Override
    public void printList() {
        Node<E> currentNode = firstNode;
        for (int i = 0; i < size; i++) {
            System.out.println(currentNode.data + " ");
            currentNode = currentNode.nextNode;
        }
    }
    
    private static class Node<E> {
        E data; // 存储数据
        Node<E> prevNode; // 存储前驱节点
        Node<E> nextNode; // 存储后继节点
        
        public Node(Node<E> prevNode, E data, Node<E> nextNode) {
            this.data = data;
            this.prevNode = prevNode;
            this.nextNode = nextNode;
        }
    }
    
    @Override
    public int size() {
        return size;
    }
    
    @Override
    public boolean contains(E e) {
        Node<E> current = firstNode;
        while (current != null) {
            if ((e == null && current.data == null) || (current.data.equals(e))) {
                return true;
            }
            current = current.nextNode;
        }
        return false;
    }
}
